﻿using System;

namespace Rotate
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            int[] arr1 = new int[] { 1, 2, 3, 4, 5, 6, 7 };
            int[] arr2 = new int[] { -1, -100, 3, 99 };
            int[] arr3 = new int[] { 1, 2 };
            Rotate3(arr1, 3);
            Rotate3(arr2, 2);
            Show(arr1);
            Show(arr2);
            Rotate3(arr3, 3);
            Show(arr3);
        }

        /*

        给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

        示例 1:

        输入: [1,2,3,4,5,6,7] 和 k = 3
        输出: [5,6,7,1,2,3,4]
        解释:
        向右旋转 1 步: [7,1,2,3,4,5,6]
        向右旋转 2 步: [6,7,1,2,3,4,5]
        向右旋转 3 步: [5,6,7,1,2,3,4]
        示例 2:

        输入: [-1,-100,3,99] 和 k = 2
        输出: [3,99,-1,-100]
        解释: 
        向右旋转 1 步: [99,-1,-100,3]
        向右旋转 2 步: [3,99,-1,-100]
        说明:

        尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
        要求使用空间复杂度为 O(1) 的 原地 算法。

        作者：力扣 (LeetCode)
        链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/
        来源：力扣（LeetCode）
        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

        */
        public static void Rotate(int[] nums, int k)
        {
            int temp = 0;
            int next = 0;
            for (int i = 0; i < k && i <= nums.Length; i++)
            {
                temp = nums[0];
                for (int j = 0; j < nums.Length; j++)
                {
                    next = nums[(j + 1) % nums.Length];
                    // 当前右移一位
                    nums[(j + 1) % nums.Length] = temp;
                    temp = next;
                }
            }
        }

        public static void Rotate2(int[] nums, int k)
        {
            int temp, prev;
            for (int i = 0; i < k; i++)
            {
                prev = nums[nums.Length - 1];
                for (int j = 0; j < nums.Length; j++)
                {
                    temp = nums[j];
                    nums[j] = prev;
                    prev = temp;
                }
            }
        }

        public static void Rotate3(int[] nums, int k)
        {
            int[] arr = new int[nums.Length];
            for (int i = 0; i < nums.Length; i++)
            {
                arr[(i + k) % nums.Length] = nums[i];
            }

            for (int i = 0; i < nums.Length; i++)
            {
                nums[i] = arr[i];
            }
        }

        public static void Show(int[] arr)
        {
            System.Console.WriteLine($"[{string.Join(",", arr)}]");
        }
    }
}
